package com.peng.leetcode.monStack;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * RemoveDuplicateLetters
 * <p>
 * 316. 去除重复字母
 * <p>
 * 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
 *
 * @author: lupeng6
 * @create: 2021/3/30 14:39
 */
public class RemoveDuplicateLetters {

    public static void main(String[] args) {
        String s = "cbacdcbc";
        System.out.println(new RemoveDuplicateLetters().removeDuplicateLetters(s));
    }


    public String removeDuplicateLetters(String s) {
        int len = s.length();
        Map<Character, Integer> charCount = new HashMap<>();

        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            charCount.putIfAbsent(c, 0);
            charCount.compute(c, (k, v) -> v + 1);
        }

        boolean[] inStack = new boolean[26];
        Deque<Character> deque = new LinkedList<>();

        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            if (!inStack[c - 'a']) {
                while (!deque.isEmpty() && deque.peekLast() > c) {
                    if (charCount.get(deque.peekLast()) == 0) {
                        break;
                    }
                    Character lastChar = deque.pollLast();
                    inStack[lastChar - 'a'] = false;
                }

                inStack[c - 'a'] = true;
                deque.offerLast(c);
            }
            charCount.compute(c, (k, v) -> v - 1);
        }

        StringBuilder builder = new StringBuilder();
        while (!deque.isEmpty()) {
            builder.append(deque.pollFirst());
        }
        return builder.toString();
    }
}
